// Problem: A - Number Coding
// Idea: Dynamic Programming, somewhat tricky to get all the details right.
// Language: C++
// Author: Ivan Vladimirov Ivanov (ivan.vladimirov.ivanov@gmail.com)

#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

typedef long long LL;

struct State
{
  int n, pos, p;
  LL last;

  State() {}

  State(int n, int pos, int p, LL last) : n(n), pos(pos), p(p), last(last) {}

  bool operator < (const State &s) const {
    if(n != s.n) return n < s.n;
    if(p != s.p) return p < s.p;
    if(pos != s.pos) return pos < s.pos;
    if(last != s.last) return last < s.last;
    return false;
  }
};

void input(void);
void solve(void);
LL dp(int n, int pos, int p, LL last);

int N, M;
char S[32];
map <State, LL> F;
LL C[20][20];

int main(void)
{
  int t;
  scanf("%d", &t);
  while(t--) {
    input();
    solve();
  }

  return 0;
}

void input(void)
{
  scanf(" %s", S);
  N = S[0] - '0';
  M = strlen(S) - 1;
}

void solve(void)
{
  for(int i = 0; i < 20; i++) C[i][0] = 1;
  for(int j = 1; j < 20; j++) C[0][j] = 0;
  for(int i = 1; i < 20; i++) for(int j = 0; j < 20; j++) {
    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }

  F.clear();
  printf("%lld\n", dp(N, 0, 9, 0));
}

LL dp(int n, int pos, int p, LL last)
{
  if(n == 0 && pos == M) return 1;

  State s(n, pos, p, last);
  if(F.count(s)) return F[s];

  LL res = 0;
  LL num = 0;
  for(int len = 1; pos + len <= M; len++) {
    //if(S[pos + 1] == '0') continue; // NB
    num = 10 * num + S[pos + len] - '0';
    if(num < last) continue;

    int r = 1;
    while(pos + r * len <= M) {
      res += dp(n - r, pos + r * len, p - r, num + 1) * C[p][r];
      LL num2 = 0;
      for(int k = 1; k <= len; k++) num2 = 10 * num2 + S[pos + r * len + k] - '0';
      if(num2 != num) break;
      r++;
    }
  }

  return F[s] = res;
}

